package num208;


/**
 * @author : DuJiabao
 * @Project : sword-finger-offer
 * @Time : 2021/5/10 1:12
 * @Desc :
 */
public class Trie1 {
  private TrieNode head = null;

  /**
   * Initialize your data structure here.
   */
  public Trie1() {
    head = new TrieNode();
  }

  /**
   * Inserts a word into the trie.
   */
  public void insert(String word) {
    TrieNode node = head;
    for (char c : word.toCharArray()) {
      if (node.alphaBet[c - 'a'] == null)
        node.alphaBet[c - 'a'] = new TrieNode();
      node = node.alphaBet[c - 'a'];
    }
    node.isWord = true;
  }

  /**
   * Returns if the word is in the trie.
   */
  public boolean search(String word) {
    TrieNode node = head;
    for (char c : word.toCharArray()) {
      node = node.alphaBet[c - 'a'];
      if (node == null) return false;
    }
    return node.isWord;
  }

  /**
   * Returns if there is any word in the trie that starts with the given prefix.
   */
  public boolean startsWith(String prefix) {
    TrieNode node = head;
    for (char c : prefix.toCharArray()) {
      node = node.alphaBet[c - 'a'];
      if (node == null) return false;
    }
    return true;
  }

  public static void main(String[] args) {
    Trie1 trie = new Trie1();
    trie.insert("apple");
    trie.insert("app");
    System.out.println(trie.search("app"));
    System.out.println(trie.search("apple"));
    //System.out.println(trie.startsWith("heq"));
  }
}

class TrieNode {
  public TrieNode[] alphaBet = new TrieNode[26];
  public boolean isWord = false;
}
